package com.leetcode.algorithm.y22.m08.w1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 797. 所有可能的路径
 * 
 * https://leetcode.cn/problems/all-paths-from-source-to-target/
 * 
 * @author jie.deng
 *
 */
class Question0797Solution01 {

	public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
		List<List<Integer>> list = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		path.offerLast(0);
		dfs(graph, path, list);
		return list;
	}

	private void dfs(int[][] graph, Deque<Integer> path, List<List<Integer>> list) {
		int prev = path.peekLast().intValue();
		int n = graph.length;
		if (prev == n - 1) {
			list.add(new ArrayList<>(path));
			return;
		}

		for (int next : graph[prev]) {
			path.offerLast(next);
			dfs(graph, path, list);
			path.pollLast();
		}
	}

}